public class Solution1745 {
    public boolean checkPartitioning(String s) {
        final int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for(int i = len - 2; i >= 0 ; i--) {
            for(int j = i + 1; j < len; j++) {
                int targetI = i + 1, targetJ = j - 1;
                boolean lastIsPalindrome = targetJ <= targetI ? true : dp[targetI][targetJ];
                if(lastIsPalindrome && s.charAt(i) == s.charAt(j)){
                    dp[i][j] = true;
                }
            }
        }

        for(int i = 1; i < len; i++) {
            for(int j = i + 1; j < len; j++) {
                if(dp[0][i - 1] && dp[i][j - 1] && dp[j][len -1]){
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args){
        Solution1745 s = new Solution1745();
        s.checkPartitioning("bbab");
    }
}
